package oct2013;

import java.util.ArrayList;
import java.util.Arrays;

public class PermutationsII {
	ArrayList<ArrayList<Integer>> res;
	int n;
	boolean[] used;
	int[] val, num;

	public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
		res = new ArrayList<ArrayList<Integer>>();
		n = num.length;
		this.num = num;
		used = new boolean[n];
		val = new int[n];
		Arrays.sort(num);
		dfs(0);
		return res;
	}

	void dfs(int d) {
		if (d == n) {
			ArrayList<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i < n; ++i) {
				list.add(val[i]);
			}
			res.add(list);
			return;
		}
		for (int i = 0; i < n; ++i) {
			if (!used[i]) {
				used[i] = true;
				val[d] = num[i];
				dfs(d + 1);
				used[i] = false;
				while (i + 1 < n && num[i + 1] == num[i])
					i++;
			}
		}
	}
}
